package com.jxb.four;

import com.jxb.tree.TreeNode;

/**
 * 类注释
 *
 * @author jiaobo
 * @date Created in 2025/1/1 16:52
 **/
public class ConstructBTfromPreAndIn_105 {

    public static void main(String[] args) {

    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(0,0,inorder.length - 1,preorder,inorder);
    }

    /**
     * @param preStart 前序数组的第一个元素
     * @param inStart  中序数组的开始元素
     * @param inEnd    中序数组的结束元素
     * @param preorder  前序数组
     * @param inorder   中序数组
     * @return com.jxb.tree.TreeNode
     * @author jiaobo
     * @date 2025/1/1 17:01
     */
    public TreeNode buildTree(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        //构建二叉树的根节点
        TreeNode root = new TreeNode(preorder[preStart]);
        //找出根节点在中序数组中的位置
        //使用map进行优化
        int inIndex = 0;
        for (int i = inStart; i<= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }
        //递归处理左右子树
        root.left = buildTree(preStart + 1,inStart,inIndex-1,preorder,inorder);
        //0+3-0+1，1
        root.right = buildTree(preStart + inIndex - inStart + 1,inIndex + 1,inEnd,preorder,inorder);
        return root;
    }




}
